/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：PairingHeap.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-05-09
Function List ：
Description   ：Pairing Heap
******************************************************/

#include "PairingHeap.h"
#include <stdlib.h>   // for malloc
#include "FatalError.h"

#define MaxSiblings 1000

struct PairNode {
    ElementType Element;
    Position    LeftChild;
    Position    NextSibling;
    Position    Prev;
};

// Static Function Lists
static Position CompareAndLink(Position First, Position Second);
static PriorityQueue CombineSiblings(Position FirstSibling);

PriorityQueue Initialize(void) {
    return NULL;
}

PriorityQueue Destroy(PriorityQueue H) {
    if (H != NULL) {
        Destroy(H->LeftChild);
        Destroy(H->NextSibling);
        free(H);
    }

    return NULL;
}

int IsEmpty(PriorityQueue H) {
    return H == NULL;
}

/* This is the basic operation to maintain order */
/* Links First and Second together to satisfy heap order */
/* Returns the resulting tree */
/* First is assumed NOT NULL */
/* First->NextSibling MUST be NULL on entry */
static Position CompareAndLink(Position First, Position Second) {
    if (Second == NULL) {
        return First;
    } else if (First->Element <= Second->Element) {
        /* Attach Second as the leftmost child of First */
        Second->Prev = First;
        First->NextSibling = Second->NextSibling;
        if (First->NextSibling != NULL) {
            First->NextSibling->Prev = First;
        }

        Second->NextSibling = First->LeftChild;
        if (Second->NextSibling != NULL) {
            Second->NextSibling->Prev = Second;
        }

        First->LeftChild = Second;

        return First;
    } else {
        /* Attach First as the leftmost child of Second */
        Second->Prev = First->Prev;
        First->Prev = Second;
        First->NextSibling = Second->LeftChild;
        if (First->NextSibling != NULL) {
            First->NextSibling->Prev = First;
        }

        Second->LeftChild = First;

        return Second;
    }
}

/* Assumes FirstSibling is NOT NULL */
static PriorityQueue CombineSiblings(Position FirstSibling) {
    static Position TreeArray[MaxSiblings];
    int NumSiblings;
    int i;
    int j;

    /* If only one tree, return it */
    if (FirstSibling->NextSibling == NULL) {
        return FirstSibling;
    }

    /* Place each subtree in TreeArray */
    for (NumSiblings = 0; FirstSibling != NULL; ++NumSiblings) {
        TreeArray[NumSiblings] = FirstSibling;
        FirstSibling->Prev->NextSibling = NULL;  /* Break links */
        FirstSibling = FirstSibling->NextSibling;
    }

    TreeArray[NumSiblings] = NULL;

    /* Combine the subtrees two at a time, */
    /* going left to right */
    for (i = 0; i + 1 < NumSiblings; i += 2) {
        TreeArray[i] = CompareAndLink(TreeArray[i], TreeArray[i + 1]);
    }

    /* j has the result of the last CompareAndLink */
    /* If an odd number of trees, get the last one */
    j = i - 2;
    if (j == NumSiblings - 3) {
        TreeArray[j] = CompareAndLink(TreeArray[j], TreeArray[j + 2]);
    }

    /* Now go right to left, merging last tree with */
    /* next to last. The result becomes the new last */
    for (; j >= 2; j -= 2) {
        TreeArray[j - 2] = CompareAndLink(TreeArray[j - 2],  TreeArray[j]);
    }

    return TreeArray[0];
}

/* Insert Item into pairing heap H */
/* Return resulting pairing heap */
/* A pointer to the newly allocated node */
/* is passed back by reference and accessed as *Loc */
PriorityQueue Insert(ElementType Item, PriorityQueue H, Position *Loc) {
    Position NewNode;

    NewNode = (Position)malloc(sizeof(struct PairNode));
    if (NewNode == NULL) {
        FatalError("Out of space!!!");
    }

    NewNode->Element = Item;
    NewNode->LeftChild = NULL;
    NewNode->NextSibling = NULL;
    NewNode->Prev = NULL;

    *Loc = NewNode;
    if (H == NULL) {
        return NewNode;
    } else {
        return CompareAndLink(H, NewNode);
    }
}

/* DeleteMin returns the new tree; */
/* To get the minimum, use FindMin */
/* This is for convenience */
PriorityQueue DeleteMin(ElementType *MinItem, PriorityQueue H) {
    Position NewRoot = NULL;

    if (IsEmpty(H)) {
        Error("Pairing heap is empty!");
    } else {
        *MinItem = H->Element;
        if (H->LeftChild != NULL) {
            NewRoot = CombineSiblings(H->LeftChild);
        }

        free(H);
    }

    return NewRoot;
}

ElementType FindMin(PriorityQueue H) {
    if (!IsEmpty(H)) {
        return H->Element;
    } else {
        Error("Pairing heap is empty!");
        return 0;
    }
}

/* Lower item in Position P by Delta */
PriorityQueue DecreaseKey(Position P, ElementType Delta, PriorityQueue H) {
    if (Delta < 0) {
        Error("DecreaseKey called with negative Delta");
    }

    P->Element -= Delta;
    if (P == H) {
        return H;
    }

    if (P->NextSibling != NULL) {
        P->NextSibling->Prev = P->Prev;
    }

    if (P->Prev->LeftChild == P) {
        P->Prev->LeftChild = P->NextSibling;
    } else {
        P->Prev->NextSibling = P->NextSibling;
    }

    P->NextSibling = NULL;

    return CompareAndLink(H, P);
}

PriorityQueue Merge(PriorityQueue H1, PriorityQueue H2) {
    if (H1 == NULL) {
        return H2;
    } else if (H2 == NULL) {
        return H1;
    } else {
        if (H1->Element < H2->Element) {
            if (H1->LeftChild != NULL) {
                H2->NextSibling = H1->LeftChild;
            }

            H1->LeftChild = H2;

            return H1;
        } else {
            if (H2->LeftChild != NULL) {
                H1->NextSibling = H2->LeftChild;
            }

            H2->LeftChild = H1;

            return H2;
        }
    }
}

Position LeftChild(Position P) {
    return P->LeftChild;
}

Position NextSibling(Position P) {
    return P->NextSibling;
}

ElementType Retrieve(Position P) {
    return P->Element;
}

// EOF

